import { TreeNode } from "../../utils/treeUtil"

/**多叉树节点 */
class NTreeNode {
    val: number
    children: NTreeNode[]
    constructor(val?: number) {
        this.val = (val === undefined ? 0 : val)
        this.children = []
    }
}
/**103. 二叉树的锯齿形层序遍历
 * - 从左到右，从右到左
 */
export function zigzagLevelOrder(root: TreeNode | null): number[][] {
    if (!root) return []
    const queue = [root]
    const res: number[][] = []
    let flag = true //false从左到右，true从右到左
    while (queue.length) {
        const tempRes: number[] = []
        const len = queue.length
        for (let i = 0; i < len; i++) {
            const node = queue.shift()
            if (node) {
                tempRes.push(node.val)
                if (node.left) queue.push(node.left)
                if (node.right) queue.push(node.right)
            }
        }
        if (flag) res.push(tempRes)
        else res.push(tempRes.reverse())
        flag = !flag
    }
    return res


}
/**429. N 叉树的层序遍历 */
export function levelOrder(root: NTreeNode | null): number[][] {
    //使用队列来辅助 使用队列实现叉树广度优先遍历
    if (!root) return []
    const queue = [root]
    const res: number[][] = []
    while (queue.length) {
        const tempRes: number[] = []
        const len = queue.length
        for (let i = 0; i < len; i++) {
            const node = queue.shift()
            if (node) {
                tempRes.push(node.val)
                queue.push(...node.children)
            }
        }
        res.push(tempRes)
    }
    return res
};